Fraction to Recurring Decimal || 3Sum Closest

发表于

Fraction to Recurring Decimal

Question

Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.

If the fractional part is repeating, enclose the repeating part in parentheses.

For example,

Given numerator = 1, denominator = 2, return “0.5”.
Given numerator = 2, denominator = 1, return “2”.
Given numerator = 2, denominator = 3, return “0.(6)”.

Analysis

主要难点在于如何找到小数点后的循环部分，并将其以正确的形式写出。

  • 利用hashmap记录已有的小数点后数字及其对应下标
  • 将原本的输入变量转换为long型，以免后续操作中出现溢出的状况。
  • 通过异或(^)判断最终结果是否为负
  • 每次求得余数remain，在下一次处理remain/denom的时候需要*10，已保证每次进行操作的被除数都包含整数部分。
  • 当在hashmap中发现已存的小数时，找到第一个重复remain的下标tmp。则substring(0,tmp)为重复小数部分之前的部分，而substring(tmp,len(result))则为剩余应该包含在括号内的部分。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
public class Solution {
    public String fractionToDecimal(int numerator, int denominator) {
        if(numerator==0)
            return "0";
        if(denominator==0)
            return "";
            
        long num=numerator,denom=denominator;
        num=Math.abs(num);
        denom=Math.abs(denom);
        HashMap<Long,Integer> flag=new HashMap<Long,Integer>();
        
        StringBuilder result=new StringBuilder();
        if((numerator<0)^(denominator<0))
            result.append("-");
        result.append(num/denom);
      
        
        long remain=(num%denom)*10;
        if(remain==0)
            return result.toString();
        result.append(".");
        
        while(remain!=0){
            if(flag.containsKey(remain)){
                String tmp1=result.toString().substring(0,flag.get(remain));
                String tmp2=result.toString().substring(flag.get(remain),result.length());
                result.delete(0,result.length());
                result.append(tmp1+"("+tmp2+")");
                break;
            }
            
            flag.put(remain,result.length());
            result.append(remain/denom);
            remain=(remain%denom)*10;
            
        }
        return result.toString();
    }
}

3Sum Closest

Question

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

For example, given array S = {-1 2 1 -4}, and target = 1.
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
Analysis
  • 最后返回加和，不需要保存下标，故只需保存与target差距最小的值max
  • 对数组排序后，在low<high的条件下，判断当前和值与target的差值是否小于max，是则赋值，否则若sum<target，移动low下标，否则移动high下表
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Solution {
    public int threeSumClosest(int[] nums, int target) {
        int size=nums.length;
        if(nums==null||size<3)
            return -1;
        int sum=nums[0]+nums[1]+nums[2];
        int max=sum;
        Arrays.sort(nums);
        for(int i=0;i<size;i++){
            int low=i+1,high=size-1;
            while(low<high){
                sum=nums[i]+nums[low]+nums[high];
                if(Math.abs(sum-target)<Math.abs(max-target)){
                    max=sum;
                }else if(sum<target){
                    low++;
                }else{
                    high--;
                }
            }
        }
        return max;
    }
}